package cn.cxq.learning.sort;

import java.util.Arrays;

/**
 * 基数排序： 经典的用空间换时间的排序算法，也称桶排序。
 */
public class CardinalSort {

    public static int[] printSort(int[] arr){

        //找最大值
        int max = 0;

        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > max) max = arr[i];
        }

        //求出循环次数
        int loop = 0;

        while (max != 0) {
            max /= 10;
            loop ++;
        }

        int[][] packets = new int[10][arr.length];

        int[] packetContent = new int[10]; //每个桶里面存的数的个数。

        for (int i = 0; i < loop; i++) {
            for (int j = 0; j < arr.length; j++) {
                int index = (int) ((arr[j]/Math.pow(10, i)) % 10);
                packets[index][packetContent[index]++] =arr[j];
            }

            //将桶中的数据按序存入数组中。
            int index = 0;

            for (int j = 0; j < packetContent.length; j++)
                if (packetContent[j] != 0){
                    for (int k = 0; k < packetContent[j]; k++)
                        arr[index ++] = packets[j][k];
                    packetContent[j] = 0;
                }



            System.out.println(Arrays.toString(arr));
        }

        return arr;
    }

    public static int[] sort(int[] arr){

        //找最大值
        int max = 0;

        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > max) max = arr[i];
        }

        //求出循环次数
        int loop = 0;

        while (max != 0) {
            max /= 10;
            loop ++;
        }

        int[][] packets = new int[10][arr.length];

        int[] packetContent = new int[10]; //每个桶里面存的数的个数。

        for (int i = 0; i < loop; i++) {
            for (int j = 0; j < arr.length; j++) {
                int index = (int) ((arr[j]/Math.pow(10, i)) % 10);
                packets[index][packetContent[index]++] =arr[j];
            }

            //将桶中的数据按序存入数组中。
            int index = 0;

            for (int j = 0; j < packetContent.length; j++)
                if (packetContent[j] != 0){
                    for (int k = 0; k < packetContent[j]; k++)
                        arr[index ++] = packets[j][k];
                    packetContent[j] = 0;
                }



        }

        return arr;
    }
}
